﻿#define _CRT_SECURE_NO_WARNINGS

#include"Tree.h"

//复制二叉树
void Copy(BTNode* T, BTNode** pNewT)
{
	if (T == NULL)
	{
		*pNewT = NULL;
		return;
	}
	if (!(*pNewT = (BTNode*)malloc(sizeof(BTNode))))
	{
		perror("malloc");
		exit(-1);
	}
	(*pNewT)->data = T->data;
	Copy(T->pleft, &((*pNewT)->pleft));
	Copy(T->pright, &((*pNewT)->pright));
}

//计算二叉树的深度
int Depth(BTNode* T)
{
	if (T == NULL)
		return 0;
	else
	{
		int m = Depth(T->pleft);
		int n = Depth(T->pright);
		if (m > n)
			return m + 1;
		else
			return n + 1;
	}
}

//统计二叉树中结点的个数
int NodeCount(BTNode* T)
{
	if (T == NULL)
		return 0;
	else
		return NodeCount(T->pleft) + NodeCount(T->pright) + 1;
}

//统计二叉树中，度为0结点的个数
int NodeCount_Zero(BTNode* T)//也就是叶子结点
{
	if (T == NULL)
		return 0;
	if (T->pleft == NULL && T->pright == NULL)
	{
		return 1;
	}
	else
		return NodeCount_Zero(T->pleft) + NodeCount_Zero(T->pright);
}

//统计二叉树中，度为1结点的个数
int NodeCount_One(BTNode* T)
{
	if (T == NULL)
	{
		return 0;
	}
	if ((T->pleft != NULL && T->pright == NULL) || (T->pleft == NULL && T->pright != NULL))
		return NodeCount_One(T->pleft) + NodeCount_One(T->pright) + 1;
	else
		return NodeCount_One(T->pleft) + NodeCount_One(T->pright);
}



//统计二叉树中，度为2结点的个数
int NodeCount_Two(BTNode* T)
{
	if (T == NULL)
		return 0;
	if (T->pleft != NULL && T->pright != NULL)
		return NodeCount_Two(T->pleft) + NodeCount_Two(T->pright) + 1;
	else
		return NodeCount_Two(T->pleft) + NodeCount_Two(T->pright);
}



//先序建立二叉树
void CreatBinaryTree(BTNode** pT)
{
	char ch;
	scanf("%c", &ch);
	if (ch == '#')							//输入'#',代表插入空节点
	{
		*pT = NULL;
	}
	else
	{
		if (!((*pT) = (BTNode*)malloc(sizeof(BTNode))))
		{
			perror("malloc");
			exit(-1);
		}
		(*pT)->data = ch;						//创建根节点
		CreatBinaryTree(&((*pT)->pleft));			//构造左子树
		CreatBinaryTree(&((*pT)->pright));			//构造右子树
	}
	return;
}

//先序遍历二叉树
void PrevOrder(BTNode* T)
{
	if (T == NULL)
	{
		printf("#");
		return;
	}
	printf("%c", T->data);
	PrevOrder(T->pleft);
	PrevOrder(T->pright);
}